package com.xcc.dataStructures.demo13_graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Graph {

    //存储图对应的邻结矩阵
    private int[][] edges;
    //存储顶点的集合
    private List<String> vertexList;
    //边的数目
    private int numOfEdges;
    //每个元素对应的被访问状态
    private boolean[] isvisited;

    public Graph(int n) {
        edges = new int[n][n];
        vertexList = new ArrayList<>(n);
        numOfEdges = 0;
    }

    /**
     * 添加顶点
     */
    private void insertVertex(String vertex) {
        vertexList.add(vertex);
    }

    /**
     * 添加边
     */
    private void insertEdges(int x,int y ,int val) {
        edges[x][y] = val;
        edges[y][x] = val;
        if (val != 0) {
            numOfEdges++;
        }
    }

    /**
     * 遍历图
     */
    private void show() {
        for (int[] edge : edges) {
            for (int i : edge) {
                System.out.print(i+"\t");
            }
            System.out.println();
        }
    }

    /**
     * 返回边的条数
     */
    public int getNumOfEdges() {
        return numOfEdges;
    }

    /**
     * 返回顶点数
     */
    public int getVertexSize() {
        return vertexList.size();
    }

    /**
     * 根据下标获取顶点
     */
    public String getVertexVal(int index) {
        return vertexList.get(index);
    }

    /**
     * 获取v1 v2 的权值
     */
    public int getWeight(int v1,int v2) {
        return edges[v1][v2];
    }

    /**
     * 获取第一个邻接结点的下标 : 不存在返回-1
     * @param index 固定的行号，查找与行号对应的列>0的下标(第一个)
     */
    public int getFirstNeighbor(int index) {
        for (int i = 0; i < getVertexSize(); i++) {
            if (edges[index][i] > 0) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 查找下一个邻接结点的下标
     */
    public int getNextNeighbor(int v1,int v2) {
        for (int i = v2 +1; i < getVertexSize(); i++) {
            if (edges[v1][i] >0) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 深度优先
     */
    public void dfs() {
        isvisited = new boolean[numOfEdges];
        for (int i = 0; i < getVertexSize(); i++) {
            if (!isvisited[i]) {
                dfs(i);
            }
        }
        System.out.println();
    }

    /**
     * 深度优先遍历
     *  1，定义初始访问结点索引v，打印结点值并标记当前已访问
     *  2，在矩阵中以v为行，找到第一个邻接结点w
     *  3，判定当这个邻接结点w存在
     *      如果这个邻接结点w未被访问，则令v为w循环调用遍历走1-2-3。(递归调用)
     *      如果这个邻接结点w已经被访问，则查找v行w列的下一个邻接结点为w
     *  4，判定这个邻接结点w不存在，则需要从下一个结点v开始从新寻找
     */
    public void dfs(int v) {
        //访问初始结点
        System.out.print(getVertexVal(v) + "->");
        isvisited[v] = true;
        int w = getFirstNeighbor(v);
        while (w != -1) {
            if (!isvisited[w]){
                dfs(w);
            }
            w = getNextNeighbor(v, w);
        }
    }

    public void bfs(int v) {
        int u ; // 表示队列的头结点对应下标
        int w ; // 邻接结点 w
        LinkedList<Integer> list = new LinkedList<>();
        System.out.print(getVertexVal(v) + "->");
        isvisited[v] = true;
        list.addLast(v);
        while (!list.isEmpty()) {
            u = list.removeFirst();
            w = getFirstNeighbor(u);
            if (w != -1) {
                if (!isvisited[w]) {
                    System.out.print(getVertexVal(w) + "->");
                    isvisited[w] = true;
                    list.addLast(w);
                }
                w = getNextNeighbor(u, w);
            }
        }
    }

    /**
     * 广度优先遍历
     */
    public void bfs() {
        isvisited = new boolean[numOfEdges];
        for (int i = 0; i < getVertexSize(); i++) {
            if (!isvisited[i]) {
                bfs(i);
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        String[] arr = {"A", "B", "C", "D", "E"};
        Graph graph = new Graph(arr.length);

        //添加顶点
        for (String ver : arr) {
            graph.insertVertex(ver);
        }

        /*
         * 添加边
         *  0 1 1 0 0
         *  1 0 1 1 1
         *  1 1 0 0 0
         *  0 1 0 0 0
         *  0 1 0 0 0
         *
         * A-B A-C B-C B-D B-E
         */
        graph.insertEdges(0,1,1);
        graph.insertEdges(0,2,1);
        graph.insertEdges(1,2,1);
        graph.insertEdges(1,3,1);
        graph.insertEdges(1,4,1);
        graph.show();

        System.out.println("深度优先遍历");
        graph.dfs();
        System.out.println("广度优先遍历");
        graph.bfs();

    }

}
